/*
 * @lc app=leetcode.cn id=106 lang=cpp
 *
 * [106] 从中序与后序遍历序列构造二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
public:
    TreeNode *traval(vector<int> &inorder, int inorderbegin, int inorderend, vector<int> &postorder, int postorderbegin, int postorderend)
    {
        //第一步
        if (postorderbegin == postorderend)
        {
            return NULL;
        }
        //第二步 根据后序遍历确定分界点
        int rootval = postorder[postorderend - 1];
        //后序遍历第一个节点是根节点
        TreeNode *root = new TreeNode(rootval);
        //如果当前为叶子节点 返回
        if (postorderend - postorderbegin == 1)
        {
            return root;
        }

        //第三步 切割中序和后序遍历数组
        //均采用   左闭右开   的区间
        int mysplit; //定义切割点
        for (mysplit = inorderbegin; mysplit < inorderend; mysplit++)
        {
            if (inorder[mysplit] == rootval)
            {
                break;
            }
        }
        //中序遍历切割数组
        int leftinorderbegin = inorderbegin; //左边界闭区间
        int leftinorderend = mysplit;        //右边界开区间

        int rightinorderbegin = mysplit + 1;
        int rightinorderend = inorderend;

        //后序遍历切割数组 需要注意 中序遍历数组大小一定与后序遍历数组大小相等
        //左闭右开 右边界取不到
        int leftpostorderbegin = postorderbegin;
        int leftpostorderend = postorderbegin + mysplit - inorderbegin; //与中序左分割区间大小相等

        int rightpostorderbegin = leftpostorderend;
        int rightpostorderend = postorderend - 1; //去除末尾元素

        //第四步 递归求解
        root->left = traval(inorder, leftinorderbegin, leftinorderend, postorder, leftpostorderbegin, leftpostorderend);
        root->right = traval(inorder, rightinorderbegin, rightinorderend, postorder, rightpostorderbegin, rightpostorderend);
        return root;
    }
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder)
    {
        if (inorder.size() == 0)
        {
            return NULL;
        }
        //区间始终是左闭右开！
        return traval(inorder, 0, inorder.size(), postorder, 0, postorder.size());
    }
};
// @lc code=end
